Today's computer systems are constantly being pushed to achieve ever-greater system performance. Computer engineers and software developers leverage a variety of techniques and approaches to increase performance. For example, software engineers may expend considerable effort optimizing computer code by utilizing space-efficient and/or time-efficient data structures and algorithms for solving particular computing problems. Research into general solutions (e.g., data structures, algorithms) aimed at solving commonly arising software problems has been prolific, though more solutions are regularly needed as new problems arise.
One problem that commonly arises when implementing software systems is that of quickly testing set membership. For example, a software system may be configured to observe a series of values over time and then, given a query value, the system may determine whether the query value was among the observed values (i.e., whether the query value is a member of the set of observed values).
This general challenge of testing set membership arises in many situations. For example, in software transactional memory systems (STMs), a processor may receive cache coherency message (i.e., probes) from other processors, each message concerning a respective position in shared memory. In response to receiving such a message, an STM may need to determine whether an uncommitted transaction being executed by the processor has accessed a memory position indicated by a received probe. Because this determination is a common task in STMs, it is desirable to quickly determine whether the received probe indicates a memory position in the access set of the executing transaction.
In other examples of testing set membership, a web server may need to determine whether it has previously served a webpage corresponding to a given URL or a garbage collector may need to quickly determine whether a given block of memory is still alive. Many other examples exist.
One solution to determining set membership is to employ a “Bloom filter”, a probabilistic data structure for testing set memberships. A Bloom filter allows false positives but not false negatives. That is, Bloom filter may only definitively conclude that a given element is not in the set of observed elements, but not that it is in the set. However, this guarantee is sufficient for many scenarios.
Software-implemented Bloom filters are often used by software applications to determine set membership in a time-efficient and/or space-efficient manner. Therefore, it may be desirable for Bloom filter implementations themselves to be highly efficient. However, traditional Bloom filters are implemented using only software constructs and in-memory data structures.